use std::collections::LinkedList;
use std::collections::linked_list::CursorMut;
use std::sync::Arc;

pub trait LruCacheItem {
	type ID:PartialEq;
	type SRC;
	type Error;
	fn id(&self) -> Self::ID;
	fn miss_read(src:&mut Self::SRC,id:Self::ID) -> Result<Arc<Self>,Self::Error>;
}

enum LruCacheLoopResult<T> {
	Find(T),
	Continue,
	Break,
}

#[derive(Debug)]
pub struct LruCache<T:LruCacheItem> {
	cap:usize,
	src:T::SRC,
	list:LinkedList<Arc<T>>,
}

impl<'a,T:LruCacheItem> LruCache<T> {
	pub fn with_capacity(cap:usize,src:T::SRC) -> Self {
		Self {
			cap:cap,
			src:src,
			list:LinkedList::new(),
		}
	}

	pub fn hit_virtual<F:Fn(&T)->bool>(&self,f:F) -> Option<Arc<T>> {
		for t in &self.list {
			if f(&t){
				return Some(t.clone())
			}
		}
		None
	}
	
	pub fn hit<F:Fn(&T)->bool>(&mut self,f:F) -> Option<Arc<T>> {
		let mut c = self.list.cursor_front_mut();
		loop {
			match Self::check_one(&mut c,&f) {
				LruCacheLoopResult::Find(t) => {
					self.list.push_front(t.clone());
					return Some(t)
				}
				LruCacheLoopResult::Break => {
					break;
				}
				LruCacheLoopResult::Continue => {
					continue;
				}
			}
		}
		None
	}
	
	fn check_one<F:Fn(&T)->bool>(c:&mut CursorMut<'_, Arc<T>>,f:F) 
					->LruCacheLoopResult<Arc<T>>  {
		match c.current() {
			Some(t) => {
				if f(t) {
					return LruCacheLoopResult::Find(
						c.remove_current().unwrap()
					)
				}
			}
			None => {
				return LruCacheLoopResult::Break
			}
		}
		c.move_next();
		LruCacheLoopResult::Continue
	}
	
	pub fn hit_with_id(&mut self,id:T::ID) -> Result<Arc<T>,T::Error>  {
		if let Some(_) = self.hit(
			|t|t.id() == id
		){ 

		}else{
			match T::miss_read(&mut self.src,id) {
				Ok(b) => {
					if self.list.len() == self.cap {
						self.list.pop_back();
					}
					self.list.push_front(b);
				}
				Err(e) => {
					return Err(e);
				}
			}
		} 
		Ok(self.list.front().unwrap().clone())
	}
	
	pub fn count_all(&self,prefix:&str) {
		print!("{}:",prefix);
		for one in &self.list {
			print!("{} ",Arc::strong_count(&one));
		}
		println!("");
	}
			
}

impl<'a,T:LruCacheItem> IntoIterator for &'a LruCache<T> {
    type Item = &'a Arc<T>;
    type IntoIter = std::collections::linked_list::Iter<'a,Arc<T>>;
    fn into_iter(self) -> Self::IntoIter {
		self.list.iter()
	}
}

pub mod cache_tests {
	use super::*;
	use std::sync::Arc;
	pub static MEM_STR:[CacheString;0x8] = [
		CacheString{g:0x0,h:0x1},
		CacheString{g:0x2,h:0x3},
		CacheString{g:0x4,h:0x5},
		CacheString{g:0x6,h:0x7},
		CacheString{g:0x8,h:0x9},
		CacheString{g:0xa,h:0xb},
		CacheString{g:0xc,h:0xd},
		CacheString{g:0xe,h:0xf},
	];
	
	#[derive(Debug,Copy,Clone,PartialEq)]
	pub struct CacheString {
		pub g:usize,
		pub h:usize,
	} 
	
	impl LruCacheItem for CacheString {
		type ID = usize;
		type SRC = ();
		type Error = ();
		fn id(&self) -> Self::ID {
			self.g/2
		}
		
		fn miss_read(_:&mut Self::SRC,id:Self::ID) -> Result<Arc<Self>,Self::Error> {
			if id < MEM_STR.len() {
				Ok(Arc::new(MEM_STR[id]))
			} else {
				Err(())
			} 
		}
	}

	pub fn test() {
		let mut cache:LruCache<CacheString> = LruCache::with_capacity(3,());
		let test_id:Vec<usize> = vec![
			5,
			6,
			4,
			3,
			2,
			9,
			7,
			1,
			1,
			0,
		];
		let test_result:Vec<_> = test_id.iter().map(|id|{
			if *id<MEM_STR.len() {
				Some(MEM_STR[*id])
			} else {
				None
			}
		}).collect();
		let mut run_result = Vec::new();
		for id in test_id {
			if let Ok(inner) = cache.hit_with_id(id) {
				run_result.push(Some(*inner));
			} else {
				run_result.push(None);
			}
		}
		for (a,b) in test_result.iter().zip(run_result.iter()) {
			match a {
				Some(s) => {
					println!("result:{:#?}",s);
				}	
				None => {
					println!("result:None");
				}
			}
			assert_eq!(a,b);
		}
		println!("LruCache:{:#?}",cache);
	}
}
